#define _CRT_SECURE_NO_WARNINGS 1

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverseBetween(struct ListNode* head, int left, int right) {
    if (head == NULL || head->next == NULL)
        return head;
    int i = 0;
    struct ListNode* sentinel = (struct ListNode*)malloc(sizeof(struct ListNode));
    sentinel->next = head;
    struct ListNode* ptail = sentinel, * prev_end = NULL, * ptail_head = NULL;
    while (ptail && ptail->next)
    {
        if (i + 1 == left)
        {
            prev_end = ptail;
            ptail_head = ptail->next;
            struct ListNode* n1 = NULL, * n2 = ptail->next, * n3 = ptail->next->next;
            i++;
            while (i <= right)
            {
                n2->next = n1;
                n1 = n2;
                n2 = n3;
                if (n3 == NULL)
                    break;
                n3 = n3->next;
                i++;
            }
            ptail->next = n1;
            ptail_head->next = n2;
            break;
        }
        else
        {
            i++;
            ptail = ptail->next;
        }
    }
    return sentinel->next;
}